package com.kehao.newcoder;

import org.junit.Test;

public class NC127Solution {

    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        int commonStrLength = 0;
        int lastIndex = 0;
        /**
         *  i 表示当公共子串的最后一个字符在str1的第i个位置，
         *  j表示str2的第j个位置 0表示没取，str1.length表示str1的最后一位
         *  dp[i][j]表示上述位置的时候的最长公共字串长度
         */
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        for (int i = 0; i < str1.length(); i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i < str2.length(); i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i < str1.length()+1; i++) {
            for (int j = 1; j < str2.length()+1; j++) {
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                    if(commonStrLength<dp[i][j]){
                        commonStrLength = dp[i][j];
                        lastIndex = i;
                    }
                }else {
                    dp[i][j] = 0;
                }
            }
        }
        return str1.substring(lastIndex-commonStrLength,lastIndex);
    }


    @Test
    public void test(){
        String str1 = "1AB2345CD";
        String str2 = "12345EF";
        String lcs = LCS(str1, str2);
        System.out.println(lcs);
    }
}
